package com.c2b.algorithm.leetcode.base;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Random;

/**
 * <a href="https://leetcode.cn/problems/design-skiplist/">设计跳表(Design Skiplist)</a>
 * <p>不使用任何库函数，设计一个 <a href='https://oi-wiki.org/ds/skiplist/'>跳表</a>。</p>
 * <p>跳表 是在 O(log(n)) 时间内完成增加、删除、搜索操作的数据结构。跳表相比于树堆与红黑树，其功能与性能相当，并且跳表的代码长度相较下更短，其设计思想与链表相似。</p>
 *
 * <p>
 * 在本题中，你的设计应该要包含这些函数：
 *      <ul>
 *          <li>bool search(int target) : 返回target是否存在于跳表中。</li>
 *          <li>void add(int num): 插入一个元素到跳表。</li>
 *          <li>bool erase(int num): 在跳表中删除一个值，如果 num 不存在，直接返回false. 如果存在多个 num ，删除其中任意一个即可。</li>
 *      </ul>
 * 注意，跳表中可能存在多个相同的值，你的代码需要处理这种情况。
 * </p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例：
 *      输入
 *          ["Skiplist", "add", "add", "add", "search", "add", "search", "erase", "erase", "search"]
 *          [[], [1], [2], [3], [0], [4], [1], [0], [1], [1]]
 *      输出
 *          [null, null, null, null, false, null, true, false, true, false]
 *      解释
 *          Skiplist skiplist = new Skiplist();
 *          skiplist.add(1);
 *          skiplist.add(2);
 *          skiplist.add(3);
 *          skiplist.search(0);   // 返回 false
 *          skiplist.add(4);
 *          skiplist.search(1);   // 返回 true
 *          skiplist.erase(0);    // 返回 false，0 不在跳表中
 *          skiplist.erase(1);    // 返回 true
 *          skiplist.search(1);   // 返回 false，1 已被擦除
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *  <li>0 <= num, target <= 2 * 10^4</li>
 *  <li>调用search, add,  erase操作次数不大于 5 * 10^4</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @see LC0705DesignHashSet_S 设计哈希集合(Design HashSet)
 * @see LC0706DesignHashMap_S 设计哈希映射(Design HashMap)
 * @see LC707DesignLinkedList_M 设计链表(Design Linked List)
 * @see LC1206DesignSkiplist_H 设计跳表(Design Skiplist)
 * @since 2024/6/28 11:10
 */
public class LC1206DesignSkiplist_H {

    static class Skiplist {

        static final class SkipNode {
            int val;
            SkipNode rightNode;
            SkipNode downNode;

            public SkipNode(int val, SkipNode rightNode, SkipNode downNode) {
                this.val = val;
                this.rightNode = rightNode;
                this.downNode = downNode;
            }
        }

        /**
         * 控制每次插入时，添加索引的概率。值越大，越容易添加。1，必定会添加。
         */
        final double P_FACTOR = 0.5;
        /**
         * 控制索引的最大层数
         */
        final int MAX_LEVEL = 32;

        SkipNode head;
        int highestLevel = 0;
        Random random = new Random();

        public Skiplist() {
        }

        public boolean search(int target) {
            SkipNode currNode = head;
            while (currNode != null) {
                if (currNode.rightNode == null || currNode.rightNode.val > target) {
                    currNode = currNode.downNode;
                } else if (currNode.rightNode.val == target) {
                    return true;
                } else {
                    currNode = currNode.rightNode;
                }
            }
            return false;
        }

        public void add(int num) {
            // 计算本次会创建几层索引
            int level = 1;
            while (level <= MAX_LEVEL && random.nextDouble() < P_FACTOR) {
                ++level;
            }
            // 若已有索引的层数，小于本次需要的层数，则需要创建新的层。给新的层创建头节点，并更新最大层数
            if (level > highestLevel) {
                for (int newLayers = level - highestLevel; newLayers > 0; --newLayers) {
                    // 为新生成的层创建虚拟头节点
                    head = new SkipNode(-1, null, head);
                }
                highestLevel = level;
            }
            // 从最高层的最左节点开始，分别找到每一层节点值小于num且最右侧的节点，放到栈中
            Deque<SkipNode> visited = new ArrayDeque<>();
            SkipNode currNode = head;
            while (currNode != null) {
                if (currNode.rightNode == null || currNode.rightNode.val >= num) {
                    visited.push(currNode);
                    currNode = currNode.downNode;
                } else {
                    // currNode.rightNode.val < num
                    currNode = currNode.rightNode;
                }
            }
            // 需要从第一层往上给1->level层分别新增节点
            SkipNode down = null;
            while (level-- > 0) {
                currNode = visited.remove();
                currNode.rightNode = new SkipNode(num, currNode.rightNode, down);
                down = currNode.rightNode;
            }
        }

        public boolean erase(int target) {
            SkipNode currNode = head;
            boolean flag = false;
            while (currNode != null) {
                if (currNode.rightNode == null || currNode.rightNode.val > target) {
                    currNode = currNode.downNode;
                } else if (currNode.rightNode.val == target) {
                    currNode.rightNode = currNode.rightNode.rightNode;
                    currNode = currNode.downNode;
                    flag = true;
                }
                // currNode.rightNode.val < target
                else {
                    currNode = currNode.rightNode;
                }
            }
            return flag;
        }
    }

    public static void main(String[] args) {
        //Skiplist skiplist1 = new Skiplist();
        //skiplist1.add(1);
        //skiplist1.add(2);
        //skiplist1.add(3);
        //System.out.println(skiplist1.search(0));
        //skiplist1.add(4);
        //System.out.println(skiplist1.search(1));
        //System.out.println(skiplist1.erase(0));
        //System.out.println(skiplist1.erase(1));
        //System.out.println(skiplist1.search(1));

        //Skiplist skiplist = new Skiplist();
        //skiplist.add(9);
        //skiplist.add(4);
        //skiplist.add(5);
        //skiplist.add(6);
        //skiplist.add(9);
        //System.out.println(skiplist.erase(2) + "：false");  // false
        //System.out.println(skiplist.erase(1) + "：false");  // false
        //skiplist.add(2);
        //System.out.println(skiplist.search(7) + "：false"); // false
        //System.out.println(skiplist.search(4) + "：true"); // true
        //skiplist.add(5);
        //System.out.println(skiplist.erase(6) + "：true");  // true
        //System.out.println(skiplist.search(5) + "：true"); // true
        //skiplist.add(6);
        //skiplist.add(7);
        //skiplist.add(4);
        //System.out.println(skiplist.erase(3) + "：false");  // false
        //System.out.println(skiplist.search(6) + "：true"); // true
        //System.out.println(skiplist.erase(3) + "：false");  // false
        //System.out.println(skiplist.search(4) + "：true"); // true
        //System.out.println(skiplist.search(3) + "：false"); // false
        //System.out.println(skiplist.search(8) + "：false"); // false
        //System.out.println(skiplist.erase(7) + "：true");  // true
        //System.out.println(skiplist.erase(6) + "：true");  // true
        //System.out.println(skiplist.search(7) + "：false"); // false
        //System.out.println(skiplist.erase(4) + "：true");  // true
        //skiplist.add(1);
        //skiplist.add(6);
        //System.out.println(skiplist.erase(3) + "：false");  // false
        //skiplist.add(4);
        //System.out.println(skiplist.search(7) + "：false"); // false
        //System.out.println(skiplist.search(6) + "：true"); // true
        //System.out.println(skiplist.search(1) + "：true"); // true
        //System.out.println(skiplist.search(0) + "：false"); // false
        //System.out.println(skiplist.search(3) + "：false"); // false
    }
}
